import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
import java.util.Scanner;
import java.util.*;


public class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    int n,k;
    public List<List<Integer>> combine(int _n, int _k) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        n = _n;
        k = _k;
        dfs(1);
        return ret;
    }

    public void dfs(int pos) {
        if(path.size() == k) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos;i <= n;i++) {
            path.add(i);
            dfs(i+1);
            path.remove(path.size()-1);
        }
    }

    public static void main1(String[] args) {
        Scanner s = new Scanner(System.in);
        int r = s.nextInt();
        int[][] path = new int[r][r];
        for(int i = 0;i < r;i++) {
            for(int j = 0;j <= i;j++) {
                path[i][j] = s.nextInt();
            }
        }

        int[][] dp = new int[r+1][r+1];


        for(int i = r-1;i >= 0;i--) {
            for(int j = i;j >= 0;j--) {
                dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j+1]) + path[i][j];
            }
        }
        System.out.println(dp[0][0]);
    }

    public static void main(String[] args) {
        int t,m;
        Scanner in = new Scanner(System.in);
        t = in.nextInt();
        m = in.nextInt();
        int[][] path = new int[2][m];


        for (int j = 0; j < m; j++) {
            path[0][j] = in.nextInt();  //时间
            path[1][j] = in.nextInt();  //价值
        }
        int[][] dp = new int[m][t];
        //在i时间内采




    }
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int x : stones) sum += x;
        int[] dp = new int[sum / 2 + 1];
        for(int i = 1;i <= n;i++) {
            for(int j = sum / 2;j >= stones[i-1];j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i-1]] + stones[i-1]);
            }
        }
        return sum - 2 * dp[sum / 2];
    }

}
